/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LTNode;  

LTNode* midNode(LTNode* head)
{
    LTNode* low = head;
    LTNode* fast = head;
    while (fast && fast->next)
    {
        low = low->next;
        fast = fast->next->next;
    }
    return low;
}
LTNode* reverselist(LTNode* head)
{
    LTNode* n1 = NULL;
    LTNode* n2 = head;
    while (n2)
    {
        LTNode* n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
    return n1;
}
void mergertwo(LTNode* l1, LTNode* l2)
{
    LTNode* l1_tmp;
    LTNode* l2_tmp;
    while (l1 && l2)
    {
        l1_tmp = l1->next;
        l2_tmp = l2->next;

        l1->next = l2;
        l1 = l1_tmp;

        l2->next = l1;
        l2 = l2_tmp;
    }
}
void reorderList(struct ListNode* head) {
    LTNode* l1 = head;
    LTNode* mid = midNode(head);
    LTNode* l2 =  mid->next;
    mid->next = NULL;
    l2 =reverselist(l2);
    mergertwo(l1,l2);
}